package com.future.datastruct.heap;

/**
 * 堆的数据结构
 *
 * 堆类型有很多种，比如：二叉堆、索引堆、二项堆、斐波那契堆、等等
 *
 * 堆在实际应用中，主要是用于优先队列等问题运用而生的数据结构，其最大值或者最小值的查找、删除、添加均可达到O(logN)的时间复杂度，
 * 不同的堆甚至更优，其主要实际应用问题有：
 * 查找最值：查找最大值的问题
 * TopK问题：可在数十亿数据中寻找前top的数据，只需少量的内存空间，和遍历O(N)的复杂度
 * 贪心算法的配合数据结构：但凡适合用贪心算法解决的应用，都可以使用堆这种数据结构。
 *
 * 具体堆类型说明如下：
 *
 * 索引堆有如下三个方面的应用。
 * 1、需要动态更新队列中元素的优先级，并使得堆结构不被破坏或重建
 * 2、多路有序序列的合并。
 * 3、需要在一个优先队列中同时需要最大值和最小值。
 *
 * @author jayzhou
 */
public interface IHeap<E> extends Iterable<E> {
    int size();    // 元素的数量

    boolean isEmpty();    // 是否为空

    void clear();    // 清空

    void add(E element);     // 添加元素

    E get();    // 获得堆顶元素

    E remove(); // 删除堆顶元素

    E replace(E element); // 删除堆顶元素的同时插入一个新元素
}
